//
// Created by mazaiting on 2024/4/27.
//
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct DLinkNode                    //双链表结点类型
{
    T data;                        //存放数据元素
    DLinkNode<T> *next;                         //指向后继结点的指针
    DLinkNode<T> *prior;                         //指向前驱结点的指针
    DLinkNode() : next(NULL), prior(NULL) {}            //构造函数
    explicit DLinkNode(T d) : data(d), next(NULL), prior(NULL) {}      //重载构造函数
};

template<typename T>
class DLinkList            //双链表类模板
{
public:
    DLinkNode<T> *dhead;        //双链表头结点
    //基本运算算法

    void CreateListF(T a[], int n)    //头插法建立双链表
    {
        DLinkNode<T> *s;
        for (int i = 0; i < n; i++)        //循环建立数据结点
        {
            s = new DLinkNode<T>(a[i]);    //创建数据结点s
            s->next = dhead->next;        //修改s结点的next成员
            if (dhead->next != NULL)    //修改头结点的非空后继结点的prior
                dhead->next->prior = s;
            dhead->next = s;        //修改头结点的next
            s->prior = dhead;        //修改s结点的prior
        }
    }

    void CreateListR(T a[], int n)    //尾插法建立双链表
    {
        DLinkNode<T> *s, *r;
        r = dhead;            //r始终指向尾结点,开始时指向头结点
        for (int i = 0; i < n; i++)        //循环建立数据结点
        {
            s = new DLinkNode<T>(a[i]);    //创建数据结点s
            r->next = s;            //将s结点插入r结点之后
            s->prior = r;
            r = s;
        }
        r->next = NULL;            //将尾结点的next域置为NULL
    }


    DLinkNode<T> *geti(int i)             //返回序号i的结点
    {
        if (i < -1) return NULL;             //i<-1返回NULL
        DLinkNode<T> *p = dhead;        //首先p指向头结点
        int j = -1;            //j置为-1(可以认为头结点序号为-1)
        while (j < i && p != NULL)             //指针p移动i+1个结点
        {
            j++;
            p = p->next;
        }
        return p;            //返回p
    }

    bool Insert(int i, T e)                 //在双链表中序号i位置插入值为e的结点
    {
        if (i < 0) return false;            //参数i错误返回false
        auto *s = new DLinkNode<T>(e);   //建立新结点s
        DLinkNode<T> *p = geti(i - 1);        //查找序号i-1的结点p
        if (p != NULL)                //找到了序号i-1的结点
        {
            s->next = p->next;            //修改s结点的next域
            if (p->next != NULL)            //修改p结点的非空后继结点的prior
                p->next->prior = s;
            p->next = s;                //修改p结点的next域
            s->prior = p;                //修改s结点的prior域
            return true;                     //插入成功返回true
        } else return false;                 //没有找到序号i-1的结点返回false
    }

    bool Delete(int i)        //在双链表中删除序号i位置的结点
    {
        if (i < 0) return false;        //参数i错误返回false
        DLinkNode<T> *p = geti(i);    //查找序号i的结点
        if (p != NULL)            //找到了序号i的结点p
        {
            p->prior->next = p->next;    //修改p结点的前驱结点的next
            if (p->next != NULL)        //修改p结点非空后继结点的prior
                p->next->prior = p->prior;
            delete p;            //释放空间
            return true;        //删除成功返回true
        } else return false;        //没有找到序号i-1的结点返回false
    }


};

template<typename T>
void Delx(DLinkList<T> &L, T x)      //求解算法
{
    DLinkNode<T> *p = L.dhead->next;      //p指向首结点
    while (p != NULL && p->data != x)      //查找第一个值为x的结点
        p = p->next;
    if (p != NULL)              //找到值为x的结点p
    {
        p->prior->next = p->next;      //删除p结点
        if (p->next != NULL)
            p->next->prior = p->prior;
        delete p;              //释放空间
    }
}

template<typename T>
void Swap(DLinkList<T> &L, T x)          //求解算法
{
    DLinkNode<T> *p = L.dhead->next, *q;  //p指向首结点
    q = NULL;
    while (p != NULL)           //查找最后一个值为x的结点q
    {
        if (p->data == x) q = p;
        p = p->next;
    }
    if (q == NULL || L.dhead->next == q)    //不存在x结点或者该结点是首结点
        return;                //直接返回
    else                    //找到了这样的结点q
    {
        DLinkNode<T> *pre = q->prior;    //pre指向结点q的前驱结点
        pre->next = q->next;        //删除q结点
        if (q->next != NULL)
            q->next->prior = pre;
        pre->prior->next = q;        //将q结点插入到pre结点之前
        q->prior = pre->prior;
        pre->prior = q;
        q->next = pre;
    }
}



